//package leetcode;
//class Solution{
//    public boolean exist(char[][] board,String word){
//        int with = board.length;
//        int high = board[0].length;
//        boolean[][] visited = new boolean[with][high];
//        for(int i=0;i<with;i++){
//            for (int j=0;j<high;j++){
//                boolean flag = check(board,visited,i,j,word,0);
//                if(flag){
//                    return true;
//                }
//            }
//        }
//        return false;
//    }
//
//    public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
//        if(board[i][j] != s.charAt(k)){
//            return false;
//        }else if(k == s.length()-1){
//            return true;
//        }
//        visited[i][j] = true;
//        int[][] directions = {{0,1},{0,-1},{1,0},{-1,0}};
//        boolean result = false;
//        for(int[] dir:directions){
//            int newi = i + dir[0];
//            int newj = j + dir[1];
//            if(newi >= 0 && newi < board.length && newj < board[0].length){
//                if(!visited[newi][newj]){
//                    boolean flag = check(board,visited,newi,newj,s,k+1);
//                    if(flag){
//                        result = true;
//                        break;
//                    }
//                }
//            }
//        }
//        visited[i][j] = false;
//        return result;
//    }
//}
//public class Test2S {
//}
